package leetcode.stack_queue;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Map;

public class Lc735 {

    public int[] asteroidCollision(int[] asteroids) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < asteroids.length; i++) {
            if (deque.isEmpty() || !canMeet(deque.peekLast(), asteroids[i])) {
                deque.offerLast(asteroids[i]);
            } else {
                boolean curAstExist = true;
                while (!deque.isEmpty() && canMeet(deque.peekLast(), asteroids[i])) {
                    if (Math.abs(asteroids[i]) < Math.abs(deque.peekLast())) {//当前的行星小
                        curAstExist = false;
                        break;
                    }
                    if (Math.abs(asteroids[i]) == Math.abs(deque.peekLast())) { //当前的行星与前面的大小相等
                        deque.pollLast();
                        curAstExist = false;
                        break;
                    }
                    deque.pollLast();//当前的行星大，前面的爆炸出队
                }
                if (curAstExist)  deque.offerLast(asteroids[i]);
            }
        }
        int[] ans = new int[deque.size()];
        int idx = 0;
        while (!deque.isEmpty())
            ans[idx++] = deque.pollFirst();
        return ans;
    }

    private boolean canMeet(int a, int b) {
        if (a > 0 && b < 0 ) return true;
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {-2,-1,1,2};
        Lc735 lc735 = new Lc735();
        Arrays.stream(lc735.asteroidCollision(arr)).forEach(System.out::println);

    }

}
